import java.util.*;



class Student {
    public String id;
    public Student(String id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "Student{" +
                "id='" + id + '\'' +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}
//Map和Set

//一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以
//模型会有两种：
//1. 纯 key 模型，比如：
//有一个英文词典，快速查找一个单词是否在词典中
//快速查找某个名字在不在通讯录中
//2. Key-Value 模型，比如：
//统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>
//梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号
//而Map中存储的就是key-value的键值对，Set中只存储了Key。

//只要是实现了Iterable接口的都可以用for-each(依靠迭代器实现)直接遍历，也就是迭代器遍历

public class Test {


    public static void main(String[] args) {
        int[] array = {2,3,6,4,9,5,9,1,65,3,8,1,5,3,6,8,2,5,7};
        Map<Integer,Integer> map = countNum(array);
        //System.out.println(map);
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            System.out.println("数字:"+entry.getKey()+"出现了："+entry.getValue()+"次!");
        }
    }
    public static void main5(String[] args) {
        Student student = new Student("123456");
        int hashcode1 = student.hashCode();
        System.out.println(hashcode1);

        Student student2 = new Student("123456");
        int hashcode2 = student2.hashCode();
        System.out.println(hashcode2);
        System.out.println("============");

        HashBuck2<Student,Integer> hash = new HashBuck2<>();
        hash.push(student,123);
        System.out.println(hash.get(student2));
    }

    public static void main4(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.push(11,1222);
        hashBuck.push(1,111);
        hashBuck.push(2,222);
        hashBuck.push(3,333);
        hashBuck.push(4,444);
        hashBuck.push(5,555);
        hashBuck.push(6,666);

        System.out.println();
        System.out.println(hashBuck.get(4));
    }


    //Set的使用：
    //Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key。
    public static void main3(String[] args) {
        Set<Integer> set = new TreeSet<>();


        //boolean add(E e) 添加元素，但重复元素不会被添加成功
        set.add(1);
        set.add(2);
        set.add(3);
        //set.add(3);//TreeSet底层就是一个TreeMap,而Map的Key的重复元素不会被添加，所以重复元素不会被添加成功

        System.out.println(set);//可直接打印也可用for-each打印
        for (Integer a : set) {
            System.out.print(a+" ");
        }
        //void clear(): 清空集合

        //boolean contains(Object o): 判断 o 是否在集合中

        //Iterator<E> iterator(): 返回迭代器

        //boolean remove(Object o): 删除集合中的 o

        //int size(): 返回set中元素的个数

        //boolean isEmpty(): 检测set是否为空，空返回true，否则返回false

        //Object[] toArray(): 将set中的元素转换为数组返回

        //boolean containsAll(Collection<?> c) :集合c中的元素是否在set中全部存在，是返回true，否则返回false

        //boolean addAll(Collection<? extendsE> c):将集合c中的元素添加到set中，可以达到去重的效果

        //1. Set是继承自Collection的一个接口类
        //2. Set中只存储了key，并且要求key一定要唯一
        //3. TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
        //4. Set最大的功能就是对集合中的元素进行去重
        //5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
        //6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
        //7. TreeSet中不能插入null的key，HashSet可以。

        //Set底层结构            TreeSet                                           HashSet
        //底层结构               红黑树                                             哈希桶
        //插入/删除/查找时间复杂度  O(log2(N))                                        O(1)
        //是否有序               关于Key有序                                         不一定有序
        //线程安全               不安全                                              不安全
        //插入/删除/查找区别       按照红黑树的特性来进行插入和删除                        1. 先计算key哈希地址 2. 然后进行插入和删除
        //比较与覆写              key必须能够比较，否则会抛出ClassCastException异常       自定义类型需要覆写equals和hashCode方法
        //应用场景                需要Key有序场景下                                    Key是否有序不关心，需要更高的时间性能
    }





    //map的使用：
    //Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。
    public static void main2(String[] args) {

        //1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
        //2. Map中存放键值对的Key是唯一的，value是可以重复的
        //3. 在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，value可以为空。但
        //是HashMap的key和value都可以为空。
        //4. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
        //5. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
        //6. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行
        //重新插入。




        //Map<Key,Value>;
        //Key:名字，代号
        //Value:出现的次数
        Map<String,Integer> map = new TreeMap<>();

        //put(key,Value)
        //设置Key对应的Value
        //重复设置Key会被覆盖
        map.put("A",1);
        map.put("B",2);
        map.put("C",3);

        //get(Key)
        //返回 key 对应的 value
        System.out.println("A出现" +map.get("A")+ "次");

        //getOrDefault(Key,defaultValue)
        //返回 key 对应的 value，key 不存在，返回默认值
        //defaultValue:自己设置的默认值
        System.out.println("B出现："+map.getOrDefault("B", 4));
        System.out.println("D出现："+map.getOrDefault("D", 4));

        //remove(key):
        //删除 key 对应的映射关系
        map.remove("A");
        System.out.println(map.get("A"));//删除之后结果为null

        //Set<K> keySet():返回所有 key 的不重复集合
        Set<String> set = map.keySet();
        System.out.println("所有 key 的不重复集合"+set);//可直接打印

        //Collection<V> values():返回所有 value 的可重复集合
        Collection<Integer> collection = map.values();
        System.out.println("返回所有 value 的可重复集合"+collection);

        //Set<Map.Entry<K, V>> entrySet():返回所有的 key-value 映射关系

        //用for-each实现(map不可以用for-each直接遍历)
        Set<Map.Entry<String,Integer>> set1 = map.entrySet();
        for (Map.Entry<String,Integer> entry : set1) {
            System.out.println("Key:" + entry.getKey()+" Val:"+entry.getValue());
        }

        //boolean containsKey(Object key)：判断是否包含 key
        //boolean containsValue(Object value)：判断是否包含 value





        //Map底层结构               TreeMap                                                     HashMap
        //底层结构                  红黑树                                                       哈希桶
        //插入/删除/查找时间复杂度     O(long2(N))                                                 O(1)
        //线程安全                  不安全                                                       不安全
        //插入/删除/查找区别          需要进行元素比较                                               通过哈希函数计算哈希地址
        //比较与覆写                 key必须能够比较，否则会抛出ClassCastException异常                自定义类型需要覆写equals和hashCode方法

        //应用场景                   需要Key有序场景下                                             Key是否有序不关心，需要更高的时间性能
    }
    //搜索树的使用
    public static void main1(String[] args) {

        BinarySearchTree bTree = new BinarySearchTree();

        //insert:插入数值
        bTree.insert(2);
        bTree.insert(10);
        bTree.insert(7);;
        bTree.insert(1);;
        bTree.insert(6);

        //search:返回搜索的值是否存在
        System.out.println(bTree.search(10));

        //remove:删除数值
        bTree.remove(10);

        System.out.println(bTree.search(10));
    }

    /*//题目：只出现一次的数字
    public int singleNumber(int[] nums) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!treeSet.contains(nums[i])) {
                treeSet.add(nums[i]);
            }else {
                treeSet.remove(nums[i]);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (treeSet.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }*/
    //题目：给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，
    // 你想知道你拥有的石头中有多少是宝石。
    //
    //字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。
    /*public int numJewelsInStones(String jewels, String stones) {
        TreeSet<Character> treeSet = new TreeSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            char ch = jewels.charAt(i);
            if (!treeSet.contains(ch)) {
                treeSet.add(ch);
            }
        }
        int size = 0;
        for (int i = 0; i < stones.length(); i++) {
            char ch = stones.charAt(i);
            if (treeSet.contains(ch)) {
                size++;
            }
        }
        return size;
    }*/
    //给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。(Map方法)
    /*public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null)  {
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        cur = head;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }*/



    //旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出
    //肯定坏掉的那些键。（Set方法）
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            String b = in.nextLine();
            func(a,b);
        }
    }
    private static void func(String str1, String str2) {
        Set<Character> set = new HashSet<>();
        for(Character s : str2.toUpperCase().toCharArray()) {
            set.add(s);
        }
        Set<Character> setBroke = new HashSet<>();
        for(Character s : str1.toUpperCase().toCharArray()) {
            if(!set.contains(s) && !setBroke.contains(s)) {
                System.out.print(s);
                setBroke.add(s);
            }
        }
    }*/

    //统计前array数组里每个数字出现的次数
    public static Map<Integer,Integer> countNum(int[] array) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (map.get(array[i]) == null) {
                map.put(array[i],1);
            }else {
                int val = map.get(array[i]);
                map.put(array[i],val+1);
            }
        }
        return map;
    }


    public List<String> topKFrequent(String[] words, int k) {

        //1.统计每个单词出现的次数
        Map<String,Integer> map = new HashMap<>();
        for (String str : words) {
            if (map.get(str) == null) {
                map.put(str,1);
            }else {
                int val = map.get(str);
                map.put(str,val+1);
            }
        }

        //2.遍历map，把前K个元素 放到小根堆当中
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(
                new Comparator<Map.Entry<String, Integer>>() {
                    //编写一个比较器,使其每进入一个元素按val都变成小根堆
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    //当val相同时，比较他们的首字母，大的放后面，小的放前面。
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                //现将前K个元素放入并自动排列成小根堆
                minHeap.offer(entry);
            }else {
                //将小根堆的堆顶元素跟map剩下的元素一一比较
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    //堆顶元素的出现频率小就弹出并交换,进入到堆中时自动排列小根堆
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {
                    //堆顶元素的出现频率一样时,比较双方的首字母按字典顺序排写并交换
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                    //其余不需要更改
                }
            }
        }
        List<String> arrays = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            //尾插入
            arrays.add(top.getKey());
        }
        Collections.reverse(arrays);
        return arrays;
    }

}
//面试问题：遍历map的几种方式都有什么？
//1.用sout遍历
//2.转为Set进行遍历
